package com.lx.algorithm.code.xly3.class04;

import java.util.Arrays;
import java.util.Comparator;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-12 11:53:04
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-12     张李鑫                     1.0         1.0 Version
 */
public class Code05 {
    /**
     * 每个信封都有长和宽两个维度的数据，A信封如果想套在B信封里面，A信封必须在长和宽上都小于B信封才行。
     * 如果给你一批信封，返回最大的嵌套层数
     */
    public static class Envelopes {
        public int height;
        public int weight;

        public Envelopes(int height, int weight) {
            this.height = height;
            this.weight = weight;
        }
    }

    public static class EnvelopeComparator implements Comparator<Envelopes> {
        @Override
        public int compare(Envelopes o1, Envelopes o2) {
            return o1.height != o2.height ? o1.height - o2.height : o2.weight - o1.weight;
        }
    }

    /**
     * 先排序 然后找最长递增子序列
     *
     * @return
     */
    public static int envelopesProblem(int[][] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        Envelopes[] envelopes = new Envelopes[arr.length];
        for (int i = 0; i < arr.length; i++) {
            envelopes[i] = new Envelopes(arr[i][0], arr[i][1]);
        }
        Arrays.sort(envelopes, new EnvelopeComparator());
        int right = 0;
        int l = 0;
        int m = 0;
        int r = 0;
        int N = arr.length;
        int[] dp = new int[N];
        int[] ends = new int[N];
        int max = 0;
        dp[0] = 1;
        ends[0] = envelopes[0].weight;
        for (int i = 1; i < arr.length; i++) {
            l = 0;
            r = right;
            while (l <= r) {
                m = (l + r) / 2;
                if (ends[l] < envelopes[i].weight) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            right = Math.max(right, l);
            dp[i] = l + 1;
            max = Math.max(dp[i], max);
            ends[l] = envelopes[i].weight;
        }
        return max;
    }

    public static void main(String[] args) {
        int[][] test = {{3, 4}, {2, 3}, {4, 5}, {1, 3}, {2, 2}, {3, 6}, {1, 2}, {3, 2}, {2, 4}};
        System.out.println(envelopesProblem(test));
    }
}
